﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/longest-subsequence-with-limited-sum/
/*
题目描述：
给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
 

示例 1：
输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：
输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。
 

提示：
n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106
*/

// 方法——二分查找
/*
思路：
既然是只需要求出子序列的和，那么nums驻足内的元素的顺序对我们求结果是不影响的，
所以我们就可以先对nums数组进行升序排序，并用一个数组f来保存nums数组的前缀和，f[i]表示的是nums数组中前
i个元素之和。
然后遍历数组queries，是用二分查找在f数组中查找出第一个满足f[i] > queries[j]的元素，
那么和小于等于queries[j]的最长子序列的长度就为i - 1。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整型的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}

// 再写一个二分查找算法
int binary_search(int left, int right, int* nums, int target) {
	assert(nums);
	int mid = 0;
	while (left < right) {
		if (nums[left] > target) {
			return left;
		}
		mid = left + (right - left) / 2;
		if (nums[mid] <= target) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	if (nums[left] > target) {
		return left;
	}
	return left;
}

int* answerQueries(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
	assert(nums && queries && returnSize);
	// 先对nums数组进行排序
	qsort(nums, numsSize, sizeof(int), cmp_int);
	int* answer = (int*)malloc(queriesSize * sizeof(int));
	*returnSize = queriesSize;
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	int* f = (int*)malloc((numsSize + 1) * sizeof(int));
	if (NULL == f) {
		perror("malloc");
		return NULL;
	}
	int i = 0;
	int j = 0;
	int sum = 0;
	for (i = 0; i < numsSize + 1; i++) {
		f[i] = sum;
		if (i < numsSize) {
			sum += nums[i];
		}
	}
	for (i = 0; i < queriesSize; i++) {
		answer[i] = binary_search(0, numsSize + 1, f, queries[i]) - 1;
	}
	return answer;
}